//
// Created by user on 2022/3/15.
//

#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

//拷贝单链表
ListNode* copyList(ListNode* head) {
    if(!head)return nullptr;
    ListNode *newNode = new ListNode(head->val);
    ListNode *p = copyList(head->next);
    newNode->next = p;
    return newNode;
}
//递归
unordered_map<Node*, Node*> map;
Node* copyRandomList(Node* head) {
    if(!head)return nullptr;
    Node *newNode = new Node(head->val);
    map.insert(pair<Node*, Node*>(head, newNode));
    newNode->next = copyRandomList(head->next);
    newNode->random = map[head->random];
    return newNode;
}

//迭代解法
unordered_map<Node*, Node*> visited;
Node* getCloneNode(Node* node) {
    if (!node) return nullptr;
    if (visited.count(node)) {
        return visited[node];
    } else {
        Node* newNode = new Node(node->val);
        visited[node] = newNode;
        return newNode;
    }
}
Node* copyRandomList1(Node* head) {
    if(!head)return nullptr;
    Node *oldNode = head;
    Node *newNode = new Node(oldNode->val);
    Node *newHead = newNode;
    while (oldNode) {
        newNode->next = getCloneNode(oldNode->next);
        newNode->random = getCloneNode(oldNode->random);
        oldNode = oldNode->next;
        newNode = newNode->next;
    }
    return visited[head];
}
